package 力扣题库;

public class p110平衡二叉树 {
    //求树的高度
    public int getHeight3(TreeNode root) {
        if (root==null) {
            return 0;
        }
        int leftHeight=getHeight3(root.left);
        int rightHeight=getHeight3(root.right);

        return Math.max(leftHeight,rightHeight)+1;
    }


    public boolean isBalanced1(TreeNode root) {
        //自上而下的时间复杂度：O(n^2)
        if (root==null) {
            return true;
        }

        int leftHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);

        return Math.abs(leftHeight-rightHeight) < 2 && isBalanced1(root.left) && isBalanced1(root.right);
    }





    //自下而上的时间复杂度：O(n)
    //求树高度的同时，当某个子树不符合 平衡二叉树
    public int getHeight2(TreeNode root) {
        if (root==null) {
            return 0;
        }
        int leftHeight=getHeight2(root.left);
        int rightHeight=getHeight2(root.right);

        if (leftHeight>=0 && rightHeight>=0 && Math.abs(leftHeight-rightHeight)<=1) {
            //能返回某树的高度需要满足 leftHeight>=0 && rightHeight>=0 && 左右子树高度差 <=1
            return Math.max(leftHeight,rightHeight)+1;
        }else {
            return -1;
        }
    }

    public boolean isBalanced(TreeNode root) {
        //平衡二叉树：左右子树的高度差不大于 1
        //当某个子树不符合 平衡二叉树的条件 时就不用再计算高度了
        return getHeight(root) >=0;
    }

    public int getHeight(TreeNode root) {
        if (root==null) {
            return 0;
        }

        int leftHeight2=getHeight(root.left);
        int rightHeight2=getHeight(root.right);

        if (leftHeight2 >= 0 && rightHeight2>=0 && Math.abs(leftHeight2-rightHeight2) <= 1) {
            //返回当前树的高度
            return Math.max(leftHeight2,rightHeight2)+1;
        }else {
            //注意 深入递归的过程中，一旦发现 某个结点的左右子树不平衡返回 -1，那么整棵树都不平衡
            return -1;
        }
    }

}
